Known in the art is an internal combustion engine provided with an NOx purification catalyst arranged in an engine exhaust passage and a fuel reformer for generating reformed gas containing hydrogen. This NOx purification catalyst stores NOx contained in exhaust gas when an air-fuel ratio of the inflowing exhaust gas is lean, and releases stored NOx when the air-fuel ratio of the inflowing exhaust gas becomes rich. At the time of engine startup, the reformed gas containing hydrogen generated at the fuel reformer is fed to the NOx purification catalyst to thereby raise the NOx removal rate of the NOx purification catalyst (for example, see Japanese Patent Publication No. 2010-270664A).